package com.hdu.hot100.arr;

public class lc41 {
    class Solution {
        public int firstMissingPositive(int[] nums)
        {
            int len = nums.length;
            for (int i = 0; i < len; i++)
            {
                while ((1 <= nums[i] && nums[i] <= len && nums[nums[i] - 1] != nums[i]))
                {
                    int index = nums[i] - 1;
                    int temp = nums[index];
                    nums[index] = nums[i];
                    nums[i] = temp;
                }
            }

            for (int i = 0; i < len; i++)
            {
                if (i + 1 != nums[i]) return i + 1;
            }

            return len;
        }
    }
}
